/*
 * Copyright 2012 The Netty Project
 *
 * The Netty Project licenses this file to you under the Apache License,
 * version 2.0 (the "License"); you may not use this file except in compliance
 * with the License. You may obtain a copy of the License at:
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations
 * under the License.
 */

package io.netty.buffer;

final class PoolSubpage<T> implements PoolSubpageMetric {

    /**代表其子页属于哪个Chunk
     *
     */
    final PoolChunk<T> chunk;
    private final int memoryMapIdx;
    private final int runOffset;
    private final int pageSize;
    /**用于记录子页的内存分配情况
     *
     */
    private final long[] bitmap;

    /**子页按双向列表进行关联，分别指向上一个节点和下一个节点
     *
     */
    PoolSubpage<T> prev;
    /**子页按双向列表进行关联，分别指向上一个节点和下一个节点
     *
     */
    PoolSubpage<T> next;

    boolean doNotDestroy;
    /**子页是按照多大内存进行划分的，如果按照1k划分，则可以划分出8个子页
     *
     */
    int elemSize;
    /**表示一个page大小除以分配的缓冲区大小, 也就是表示当前page被划分了多少分
     *
     */
    private int maxNumElems;
    /**表示bitmap的实际大小, 刚才我们分析过, bitmap初始化的大小为8, 但实际上并不一定需要8个元素, 元素个数要根据page切分的子块而定, 这里的大小是所切分的子块数除以64
     *
     */
    private int bitmapLength;
    /**表示下一个可用的bitmapIdx，在被释放的时候会被标记，标记被释放的子块对应bitmapIdx的下标；如果小于0表示没有被释放的子块，则通过findNextAvail方法进行查找
     *
     */
    private int nextAvail;
    /**表示剩余可用的块数
     *
     */
    private int numAvail;

    // TODO: Test if adding padding helps under contention
    //private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;

    /** Special constructor that creates a linked list head */
    PoolSubpage(int pageSize) {
        chunk = null;
        memoryMapIdx = -1;
        runOffset = -1;
        elemSize = -1;
        this.pageSize = pageSize;
        bitmap = null;
    }

    /**
     * @param head 传入head, 就是我们刚才提到过的tinySubpagePools属性中的节点, 如果我们分配的16字节的缓冲区, 则这里对应的就是第一个节点
     * @param chunk
     * @param memoryMapIdx
     * @param runOffset
     * @param pageSize
     * @param elemSize
     */
    PoolSubpage(PoolSubpage<T> head, PoolChunk<T> chunk, int memoryMapIdx, int runOffset, int pageSize, int elemSize) {
        this.chunk = chunk;
        this.memoryMapIdx = memoryMapIdx;
        this.runOffset = runOffset;
        this.pageSize = pageSize;
        bitmap = new long[pageSize >>> 10]; // pageSize / 16 / 64
        init(head, elemSize);
    }

    /**这里详细介绍一下有关bitmap, 这里是个long类型的数组, long数组中的每一个值, 也就是long类型的数字, 其中的每一个比特位, 都标记着page中每一个子块的内存是否已分配, 如果比特位是1, 表示该子块已分配, 如果比特位是0, 表示该子块未分配, 标记顺序是其二进制数从低位到高位进行排列
     * <br/>这里, 我们应该知道为什么bitmap大小要设置为子块数量除以64, 因为long类型的数字是64位, 每一个元素能记录64个子块的数量, 这样就可以通过子page个数除以64的方式决定bitmap中元素的数量。
     * <br/>如果子块不能整除64, 则通过元素数量+1方式, 除以64之后剩余的子块通过long中比特位由低到高进行排列记录，其中bitmap数组大小应该是pageSize/elemSize/64
     *
     * @param head
     * @param elemSize
     */
    void init(PoolSubpage<T> head, int elemSize) {
        doNotDestroy = true;
        // 表示保存当前分配的缓冲区大小, 这里我们以256字节举例, 所以这里是256
        this.elemSize = elemSize;
        if (elemSize != 0) {
        	// 这里初始化了两个属性maxNumElems, numAvail, 值都为pageSize/elemSize, 表示一个page大小除以分配的缓冲区大小, 也就是表示当前page被划分了多少分，numAvail则表示剩余可用的块数, 由于第一次分配都是可用的, 所以numAvail=maxNumElems
	        maxNumElems = numAvail = pageSize / elemSize;
            nextAvail = 0;
            // bitmapLength表示bitmap的实际大小, 刚才我们分析过, bitmap初始化的大小为8, 但实际上并不一定需要8个元素, 元素个数要根据page切分的子块而定, 这里的大小是所切分的子块数除以64
	        bitmapLength = maxNumElems >>> 6;
            if ((maxNumElems & 63) != 0) {
            	// 不能整除64的，需要+1，相当于有一个存不满
                bitmapLength ++;
            }

            for (int i = 0; i < bitmapLength; i ++) {
            	// bitmap标识哪个子page被分配: 0标识未分配, 1表示已分配
                bitmap[i] = 0;
            }
        }
        addToPool(head);
    }

    /**创建完SubPage，就可以通过subpage.allocate方法进行内存分配了
     * <br/>Returns the bitmap index of the subpage allocation.
     */
    long allocate() {
        if (elemSize == 0) {
            return toHandle(0);
        }

        if (numAvail == 0 || !doNotDestroy) {
            return -1;
        }

        // 取一个bitmap中可用的id(绝对id)
	    // 其中bitmapIdx表示从bitmap中找到一个可用的bit位的下标, 注意, 这里是bit的下标, 并不是数组的下标, 我们之前分析过, 因为每一比特位代表一个子块的内存分配情况, 通过这个下标就可以知道那个比特位是未分配状态
        final int bitmapIdx = getNextAvail();

        // 找到可用的bitmapIdx之后, 通过 int q = bitmapIdx >>> 6 获取bitmap中bitmapIdx所属元素的数组下标
		// int r = bitmapIdx & 63  表示获取bitmapIdx的位置是从当前元素最低位开始的第几个比特位
		// bitmap[q] |= 1L << r 是将bitmap的位置设置为不可用, 也就是比特位设置为1, 表示已占用
		// 然后将可用子配置的数量numAvail减一
		// 如果没有可用子page的数量, 则会将PoolArena中的数组tinySubpagePools所关联的subpage进行移除

        // 除以64(bitmap数组的下标)
        int q = bitmapIdx >>> 6;
        // 除以64取余, 其实就是当前绝对id的偏移量
        int r = bitmapIdx & 63;
        assert (bitmap[q] >>> r & 1) == 0;
        bitmap[q] |= 1L << r;

        // 可用的子page-1
        if (-- numAvail == 0) {
        	// 如果可用的子page为0，则移除相关子page
            removeFromPool();
        }

        return toHandle(bitmapIdx);
    }

    /**
     * @return {@code true} if this subpage is in use.
     *         {@code false} if this subpage is not used by its chunk and thus it's OK to be released.
     */
    boolean free(PoolSubpage<T> head, int bitmapIdx) {
        if (elemSize == 0) {
            return true;
        }
        // 找到bitmap数组的第几个long元素，再找到这个long元素的64位里的第几位
        int q = bitmapIdx >>> 6;
        int r = bitmapIdx & 63;
        assert (bitmap[q] >>> r & 1) != 0;
        // 置为0
        bitmap[q] ^= 1L << r;

        setNextAvail(bitmapIdx);

        // 如果原先可用的位已经是0了，这次加了1，则可以再把这个SubPage挪回到Pool里
        if (numAvail ++ == 0) {
            addToPool(head);
            return true;
        }

        if (numAvail != maxNumElems) {
            return true;
        } else {
        	// 处理当前的SubPage已经全部用完的情况
            // Subpage not in use (numAvail == maxNumElems)
            if (prev == next) {
                // Do not remove if this subpage is the only one left in the pool.
            	// 当Pool里只有一个SubPage时不要移除
                return true;
            }

            // Remove this subpage from the pool if there are other subpages left in the pool.
            // 如果Pool里还有其它的SubPage，则把这个用完的SubPage移除Pool
            doNotDestroy = false;
            removeFromPool();
            return false;
        }
    }

    /**这里的head我们刚才讲过, 是Arena中数组tinySubpagePools中的元素, 通过以上逻辑, 就会将新创建的Subpage通过双向链表的方式关联到tinySubpagePools中的元素, 我们以256字节为例（挂在了256B的下面）,
     * <br/>这样, 下次如果还需要分配256字节的内存, 就可以通过tinySubpagePools找到其元素关联的subpage进行分配了
     * @param head
     */
    private void addToPool(PoolSubpage<T> head) {
        assert prev == null && next == null;
        prev = head;
        next = head.next;
        next.prev = this;
        head.next = this;
    }

    private void removeFromPool() {
        assert prev != null && next != null;
        prev.next = next;
        next.prev = prev;
        next = null;
        prev = null;
    }

    private void setNextAvail(int bitmapIdx) {
        nextAvail = bitmapIdx;
    }

    /**这里从当前元素的第一个比特位开始找, 直到找到一个标记为0的比特位, 并返回当前比特位的下标
     * @return
     */
    private int getNextAvail() {
        int nextAvail = this.nextAvail;
        if (nextAvail >= 0) {
            this.nextAvail = -1;
            return nextAvail;
        }
        return findNextAvail();
    }

    private int findNextAvail() {
    	// 当前long数组
        final long[] bitmap = this.bitmap;
        // 获取其长度
        final int bitmapLength = this.bitmapLength;
        for (int i = 0; i < bitmapLength; i ++) {
        	// 第i个
            long bits = bitmap[i];
            // 取反不等于0，说明64位没有全部占满
            if (~bits != 0) {
            	// 这里会遍历bitmap中的每一个元素, 如果当前元素中所有的比特位并没有全部标记被使用, 则通过findNextAvail0(i, bits)方法挨个往后找标记未使用的比特位
                return findNextAvail0(i, bits);
            }
        }
        return -1;
    }

    private int findNextAvail0(int i, long bits) {
    	// 当前的page被分成了多少份
        final int maxNumElems = this.maxNumElems;
        // 乘以64，代表当前long的第一个下标
        final int baseVal = i << 6;

        for (int j = 0; j < 64; j ++) {
        	// 第一位为0(如果是2的倍数, 则第一位就是0)
            if ((bits & 1) == 0) {
            	// 这里相当于加, 将i*64之后加上j, 获取绝对下标
                int val = baseVal | j;
                // 小于块数(不能越界)
                if (val < maxNumElems) {
                    return val;
                } else {
                    break;
                }
            }
            // 当前下标不为0，说明被占用了
	        // 右移一位
            bits >>>= 1;
        }
        // 说明没有空闲位置
        return -1;
    }

    /**最后通过toHandle(bitmapIdx)获取当前子块的handle, 上一小节我们知道handle指向的是当前chunk中的唯一的一块内存
     * @param bitmapIdx
     * @return
     */
    private long toHandle(int bitmapIdx) {
    	// (long) bitmapIdx << 32 是将bitmapIdx右移32位, 而32位正好是一个int的长度, 这样, 通过 (long) bitmapIdx << 32 | memoryMapIdx 计算, 就可以将memoryMapIdx, 也就是page所属的下标的二进制数保存在 (long) bitmapIdx << 32 的低32位中
        // 0x4000000000000000L是一个最高位是1并且所有低位都是0的二进制数, 这样通过按位或的方式可以将 (long) bitmapIdx << 32 | memoryMapIdx 计算出来的结果保存在0x4000000000000000L的所有低位中, 这样, 返回对的数字就可以指向chunk中唯一的一块内存
    	return 0x4000000000000000L | (long) bitmapIdx << 32 | memoryMapIdx;
    }

    @Override
    public String toString() {
        final boolean doNotDestroy;
        final int maxNumElems;
        final int numAvail;
        final int elemSize;
        if (chunk == null) {
            // This is the head so there is no need to synchronize at all as these never change.
            doNotDestroy = true;
            maxNumElems = 0;
            numAvail = 0;
            elemSize = -1;
        } else {
            synchronized (chunk.arena) {
                if (!this.doNotDestroy) {
                    doNotDestroy = false;
                    // Not used for creating the String.
                    maxNumElems = numAvail = elemSize = -1;
                } else {
                    doNotDestroy = true;
                    maxNumElems = this.maxNumElems;
                    numAvail = this.numAvail;
                    elemSize = this.elemSize;
                }
            }
        }

        if (!doNotDestroy) {
            return "(" + memoryMapIdx + ": not in use)";
        }

        return "(" + memoryMapIdx + ": " + (maxNumElems - numAvail) + '/' + maxNumElems +
                ", offset: " + runOffset + ", length: " + pageSize + ", elemSize: " + elemSize + ')';
    }

    @Override
    public int maxNumElements() {
        if (chunk == null) {
            // It's the head.
            return 0;
        }

        synchronized (chunk.arena) {
            return maxNumElems;
        }
    }

    @Override
    public int numAvailable() {
        if (chunk == null) {
            // It's the head.
            return 0;
        }

        synchronized (chunk.arena) {
            return numAvail;
        }
    }

    @Override
    public int elementSize() {
        if (chunk == null) {
            // It's the head.
            return -1;
        }

        synchronized (chunk.arena) {
            return elemSize;
        }
    }

    @Override
    public int pageSize() {
        return pageSize;
    }

    void destroy() {
        if (chunk != null) {
            chunk.destroy();
        }
    }
}
